﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/intersection-of-two-arrays-ii/
/*
题目描述：
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，
应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。


示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
 
提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
 

进阶：
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
*/

// 方法1——排序后双指针
/*
思路：
在对两个数组进行排序后，我们让两个指针p1和p2分别指nums1和nums2的起始元素。
当p1和p2所指向的元素相等时，就将其写入答案数组，并且p1和p2都向后移动一位，
当p1和p2所指向的元素不相等时，优先让指向元素较小的指针向后移动一位。
只有有一个指针指向了数组的末尾，循环就可以停止。
*/

// 有了一行思路，那我们写起代码来也就水到渠成了：
// 先写一个函数，比较两个整数的大小
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
	assert(nums1 && nums2);
	// 先对两个数组进行排序
	qsort(nums1, nums1Size, sizeof(nums1[0]), cmp_int);
	qsort(nums2, nums2Size, sizeof(nums2[0]), cmp_int);
	int min = nums1Size < nums2Size ? nums1Size : nums2Size;
	int* ans = (int*)malloc(min * sizeof(nums1[0]));
	if (NULL == ans) {
		perror("intersect");
		return NULL;
	}
	int n = 0;
	int p1 = 0;
	int p2 = 0;
	while ((p1 < nums1Size) && (p2 < nums2Size)) {
		if (nums1[p1] == nums2[p2]) {
			ans[n] = nums1[p1];
			p1++;
			p2++;
			n++;
		}
		else {
			if (nums1[p1] < nums2[p2]) {
				p1++;
			}
			else {
				p2++;
			}
		}
	}
	*returnSize = n;
	return ans;
}
// 时间复杂度：O(mlogm + nlogn)，m和n为两个数组的元素个数，对两个数进行排序的时间复杂度为O(mlogm+nlogn),
// 用双指针进行遍历的时间复杂度为O(m+n)故最终的时间爱你复杂度为O(mlogm+nlogn)
// 空间复杂度：O(min(m,n))，m和n为两个数组的元素个数，我们取m和n的较小值来作为答案数组的长度，故空间复杂度为O(min(m,n))。

